package com.bee.剑指offer;

import java.util.*;

/**
 * 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
 *
 * @version 1.0.0
 * @Author yong.Mr
 * @data 2021-05-16
 */
public class 字符串的排列全排列回溯算法 {

    private static final ArrayList<String> RESULT = new ArrayList<String>();

    private static final Stack<Character> STACK = new Stack<Character>();

    public static ArrayList<String> Permutation(String str) {
        if(str.length() > 9) {
            return RESULT;
        }
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        paiLie(chars);
        return RESULT;
    }

    public static void paiLie(char[] chars) {
        if(chars.length <= 0) {
            Iterator<Character> iterator = STACK.iterator();
            StringBuilder stringBuilder = new StringBuilder();
            while (iterator.hasNext()) {
                stringBuilder.append(iterator.next());
            }
            if(!RESULT.contains(stringBuilder.toString())) {
                RESULT.add(stringBuilder.toString());
            }
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            char[] temp = new char[chars.length - 1];
            System.arraycopy(chars, 0, temp, 0, i);
            System.arraycopy(chars, i + 1, temp, i, chars.length - i - 1);
            STACK.push(chars[i]);
            paiLie(temp);
            STACK.pop();
        }

    }

    public static void pai(char[] chars,int target,int cur) {
        if(target == cur) {
            System.out.println(STACK.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if(STACK.contains(chars[i])) {
                continue;
            }
            STACK.add(chars[i]);
            pai(chars,target,++cur);
            STACK.pop();
        }

    }

    public static void main(String[] args) {
        pai("adada".toCharArray(),3,0);
        System.out.println(RESULT);
    }
}
